package HuffmanCode;

import java.nio.charset.StandardCharsets;
import java.util.*;

/**
 * 手动实现一个哈夫曼编码，该编码相当于是一个算法，是一种无损压缩数据的算法。
 */
public class HuffmanCode {

    public static void main(String[] args) {
        String str = "i like like like java do you like a java";//长度40个字符
        //将字符串转化为字节数组
        byte[] bytes = str.getBytes();
        String str2 = "";
        for (byte aByte : bytes) {
            str2 += aByte;
        }
        System.out.println(bytes.length);
        System.out.println("----------------------------");
        //根据一个字节数组，生成一个哈夫曼树
        Node huffmanTree = createHuffmanTree(bytes);
        //将这个哈夫曼树，进行前序输出
        huffmanTree.preOrder();
        System.out.println("--------------------------");
        //测试生成哈夫曼编码
        Map<Byte, String> huffmanCodeMap = createHuffmanCodeMap(huffmanTree);
        System.out.println(huffmanCodeMap);
        System.out.println("--------------------------");

        //测试压缩算法
        byte[] zip = zip(bytes, huffmanCodeMap);
        System.out.println(zip.length);
        System.out.println(Arrays.toString(zip));
        System.out.println("--------------------------");

        //测试一下，整体封装后的压缩方法
        byte[] bytes1 = huffmanZip(bytes);
        System.out.println(bytes1.length);
        System.out.println(Arrays.toString(bytes1));

    }

    /**
     * 将生成哈夫曼压缩字节数组的所有方法，全部封装一下，方便我们调用
     * @param bytes：原始字符串对应的字节数组
     * @return ：返回的是原始字符串压缩后的哈夫曼编码字节数组
     */
    public static byte[] huffmanZip(byte[] bytes){
        //根据原始字节数组生成一颗哈夫曼树
        Node huffmanTree = createHuffmanTree(bytes);
        //再根据这个哈夫曼树，生成对应的哈夫曼编码表
        Map<Byte, String> huffmanCodeMap = createHuffmanCodeMap(huffmanTree);
        //再根据原始字节数组，以及对应的哈夫曼编码表，生成压缩后的哈夫曼编码字节数组
        byte[] zip = zip(bytes, huffmanCodeMap);
        return zip;
    }

    /**
     *  编写一个方法将字符串对应的byte[]数组 通过生成的哈夫曼编码表 返回一个哈夫曼编码 压缩后的byte数组
     * @param bytes:字符串对应的字节数组
     * @param map：根据字节数组，生成的哈夫曼编码表
     * @return ：返回哈夫曼树编码处理后的byte[]
     */
    public static byte[] zip(byte[] bytes,Map<Byte,String> map){
        StringBuilder stringBuilder = new StringBuilder();
        //遍历字节数组中的每一个字节
        for (byte aByte : bytes) {
            //根据每一个字节获取对应的哈夫曼编码，并且依次拼接在一起
            stringBuilder.append(map.get(aByte));//结果是一串2进制编码
        }
//        System.out.println(stringBuilder);//输出一下哈夫曼编码
        //再将二进制编码转化为十进制
        //将二进制每八个，分为一段，最后若不足八位，则加一
        int len = (stringBuilder.length() + 7) / 8;//统计总共有多少个八位
        //创建一个字节数组，保存压缩后的字节
        byte[] huffmanCodeByte = new byte[len];
        //创建一个变量作为头索引
        int index = 0;
        for (int i = 0; i < stringBuilder.length(); i += 8 ) {
            String strByte;
            if(i + 8 > stringBuilder.length()) {// 不够8位
                strByte = stringBuilder.substring(i);  // 从i开始，默认到结尾结束
            }else {
                strByte = stringBuilder.substring(i, i + 8);
            }
            //将二进制转换位十进制
            huffmanCodeByte[index++] = (byte)Integer.parseInt(strByte, 2);
        }
        return huffmanCodeByte;

    }

    //根据哈夫曼树的根节点，生成各个叶子节点的哈夫曼编码，并将编码放入map中
    static Map<Byte,String> huffmanCodeMap = new HashMap<>();
    //在生成哈夫曼编码表时 需要拼接路径  定义一个stringBuilder 存储某个叶子节点的路径，这个路径就是这个叶子节点的最终哈夫曼编码
    static StringBuilder stringBuilder = new StringBuilder();//默认为空

    // 为了调用方便 重载getCodes
    public static Map<Byte, String> createHuffmanCodeMap(Node root) {
        if (root == null){
            return null;
        }
//        // 处理root的左子树
//        createHuffmanCodeMap(root.left, "0", stringBuilder);
//        // 处理root的右子树
//        createHuffmanCodeMap(root.right, "1", stringBuilder);

        createHuffmanCodeMap(root,"",stringBuilder);//也可用这一行代码替换
        return huffmanCodeMap;

    }

    /**
     *  将传入的哈夫曼树根节点的所有叶子节点的哈夫曼编码得到 , 并放入到 huffmanCodeMap 集合中
     * @param node:哈夫曼树根节点
     * @param code：路径 左子节点为 0 右子节点为 1
//     * @param stringBuilder：拼接路径 StringBuilder stringBuilder
     */
    private static void createHuffmanCodeMap(Node node,String code,StringBuilder stringBuilder){
        /**
         * 下面三段代码有何异同? 待解决。。。。。。。
         */
        //依次拼接路径
//        String stringBuilder2 = string + code;//哈夫曼编码正确

        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
        stringBuilder2.append(code);//哈夫曼编码正确

//        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder.append(code));//哈夫曼编码错误

//        StringBuilder stringBuilder2 = stringBuilder.append(code);//哈夫曼编码错误

        if (node != null) {
            if (node.data == null) {
                //若该节点是非叶子节点，则进行递归处理
                //向左递归
                createHuffmanCodeMap(node.left,"0",stringBuilder2);
                //向右递归
                createHuffmanCodeMap(node.right,"1",stringBuilder2);
            }else {
                //遇见叶子节点就跳出递归,并将该节点放入哈夫曼编码集合中去
                huffmanCodeMap.put(node.data,stringBuilder2.toString());
            }
        }
    }

    //将字节数组转化为一颗哈夫曼树
    public static Node createHuffmanTree(byte[] bytes){
        //创建一个集合存储哈夫曼树
        List<Node> nodeList = new ArrayList<>();
        //创建一个map集合
        HashMap<Byte, Integer> map = new HashMap<>();
        //将每次从字节数组，遍历出来的数据作为key，该数据在字节数组中出现的次数作为value值，并放到map集合中去
        for (byte aByte : bytes) {
            Integer count = map.get(aByte);
            if (count == null) {
                //若为空表示，map中不存在这个数据,则直接放入map集合
                map.put(aByte,1);
            }else {
                //若有重复的数据，则不再创建新节点，而是给之前创建的相同节点的权值加一
                //若已经存在，则权值加一
                map.put(aByte,++count);
            }
        }
        //测试一下，是否正确的将字节数组转换为对应的map集合
//        System.out.println(map);

        //遍历map集合，将每个键值对构建成一个节点，并放入list集合中去，下面构建哈夫曼树要用
        for (Map.Entry<Byte, Integer> entry : map.entrySet()) {
            Node node = new Node(entry.getKey(),entry.getValue());
            nodeList.add(node);
        }

        if (nodeList.size() == 0) {
            System.out.println("数组为空 无法构建哈夫曼树");
            return null;
        }
        //构建哈夫曼树,节点集合剩下的最后一个节点，就是构造完成的哈夫曼树的根节点
        while (nodeList.size() > 1){
            //对节点集合进行排序
            Collections.sort(nodeList);
            //取出list集合中第一个最简节点
            Node nodeLeft = nodeList.get(0);
            //取出list集合中第二个最简节点
            Node nodeRight = nodeList.get(1);
            //构建父节点,数据为空，但是权值是前两个节点权值和
            Node parent = new Node(null,nodeLeft.weight + nodeRight.weight);
            parent.left = nodeLeft;
            parent.right = nodeRight;
            //将处理过的数据从集合中删除
            nodeList.remove(nodeLeft);
            nodeList.remove(nodeRight);
            //再将父节点添加到集合中去
            nodeList.add(parent);
        }
        return nodeList.get(0);
    }

    //前序遍历方法
    public static void preOrder(Node node){
        if (node == null) {
            System.out.println("根节点为空，不能遍历输出！");
            return;
        }
        //若不为空，则调用节点中的前序输出方法
        node.preOrder();
    }
}

//构建哈夫曼树的节点元素，带数据与权值
class Node implements Comparable<Node>{
    Byte data; //以字节格式存储单个字符
    int weight; //存储权值
    Node left;  //指向左节点
    Node right; //指向右节点

    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }

    //自然排序
    @Override
    public int compareTo(Node o) {
        //从小到大排序
        return this.weight - o.weight;
    }

    //实现前序遍历
    public void preOrder(){
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }
}